1551. Mötərizələrin düzümünü nizamlamaq

Verilmiş mötərizələr sətrində ən az sayda mötərizənin yerini elə dəyişmək lazımdır ki, nəticədə düzgün ifadə alınsan. Əlavə etmək və ya qoşmaq olmaz..

Cəmi üç növ: adi -(), kvadrat -[] və fiqurlu -{} mötərizədən istifadə olunur. Hər mötərizə cütü açılan ('(', '[', '{' ) və bağlanan (')', ']', '}') simvollardan ibarət olur.

Düzgün yə aşağıdakı kimi tərif verək:

· Boş ifadə -düzgündür.

· Əgər s düzgündürsə, onda (S), [S] və {s} -də düzgündür.

· Əgər s və t ifadəəri düzgündürsə, onda st –də düzgündür

Məsələn, "([{}])", "" və "(){}[]" sətirləri düzgündür, lakin, "([}]", "([)]" və "{" yox.

Verilmiş mötərizələr sətrində ən az sayda mötərizənin yerini elə dəyişmək lazımdır ki, nəticədə düzgün ifadə alınsan.

Giriş. Hər sətirdə cüt sayda '(', ')', '[', ']' və '{', '}' simvolları var. Hər sətrin uzunluğu 50 –dən çox deyil.

Çıxış. Hər sətir üçün dəyişiləcək simvolların minimal sayı çıxarılır.

Girişə nümunə

([{}])()[]{}

([)]

([{}[]

Çıxışa nümunə

0

2

1

Həlli

Dinamik proqramlama

Alqoritmin analizi

s_is_i+1…s_j-1s_j alt sətrinin düzgün olması üçün dəyişiləcək simvolların ən az sayını f(i, j) götürək. O zaman:

1. f(i, j) = 0 , i > j olarsa, çünki bu halda alt sətir boşdur.

2. f(i, j) = f(i + 1, j – 1) + enc(s_i ,s_j). Elə edək ki, s_i simvolu açılan, s_j isə ona müvafiq bağlanan mötərizə olsun.

Daha sonra rekursiv olaraq s_i+1…s_j-1 alt sətrinə baxırıq.

enc(s_i ,s_j) funksiyası:

а) s_i simvolu açılan, s_j isə ona müvafiq bağlanan mötərizə olduqda 0 verir.;

б) s_i simvolu bağlanan, s_j isə ona müvafiq açılan mötərizə olduqda 2 verir;

в) Dihər hallarda isə 1 verir. Bu halda s_i və ya s_j simvollarından birini dəyişmək olar ki, onlar düzgün cüt olsun.

3. f(i, j) = (f(i, k) + f(k + 1, j)). s_is_i+1…s_j-1s_j alt sətrinə iki düzgün s_i…s_k və s_k+1…s_j.mötərizə strukturunun ardıcıllığı kimi baxırıq. s_i…s_k alt sətrinin uzunluğu cütdür, demək k , i + 1, i + 3, …, j – 2 qiymətləri alır. .

Alqoritmin realizə olunması

m massivinin m[i][j] elementi f(i, j).qiymətinə bərabərdir. Girişi s massivinə veririk..

int m[51][51], res;

char s[51];

enc(c, d).funksiyasını realizə edirik.

int enc(char c, char d)

{

string p = "([{)]}";

Əgər c bağlanan, d isə açılan mötərizə olarsa onda funksiya 2 cavabı verər..

if (p.find(c) / 3 > 0 && p.find(d) / 3 < 1) return 2;

Əgər c və d müvafiq mötərizələr isə onda cavab 0 olar. Əgər onlar düzgün yerləşməyibsə onda funksiya əvvəlki sətirdə 2 cavabı verir.

if (p.find(c) % 3 == p.find(d) % 3 && c != d) return 0;

Bütün qalan hallarda 1 verilir.

return 1;

}

f(i, j) funksiyası s_is_i+1…s_j-1s_j alt sətrini düzgün formaya gətirmək üçün lazım olan simvolların minimal sayını verir.

int f(int i, int j)

{

int k;

if (i > j) return 0;

if (m[i][j] >= 0) return m[i][j];

int r = f(i+1,j-1) + enc(s[i],s[j]);

for(k = i + 1; k < j; k += 2)

r = min(r,f(i,k) + f(k+1,j));

return m[i][j] = r;

}

Proqramın əsas hissəsi. Cavab f(0, |s| – 1) olar. Burada s – giriş sətirdir..

while(gets(s))

{

memset(m,-1,sizeof(m));

res = f(0,strlen(s) - 1);

printf("%d\n",res);

}